//
// Created by Leon Gong on 2022/3/29.
//


#include <bits/stdc++.h>
#include <u.h> // 包装了一些常用函数，目录在 lib/u.h

using namespace std;

void msort(vector<int> &v, int s, int t) {
    if (s == t) return;

    // 临时保存这个分组的结果大小为 t-s+1
    vector<int> ret = vector<int>(t - s + 1);

    int mid = (s + t) / 2;
    msort(v, s, mid); //左边
    msort(v, mid + 1, t); //右边

    int i = s, j = mid + 1, k = 0;
    while (i <= mid && j <= t) {
        if (v[i] <= v[j]) {
            ret[k] = v[i];
            i++;
            k++;
        } else {
            ret[k] = v[j];
            j++;
            k++;
        }
    }

    while (i <= mid) {
        ret[k] = v[i];
        i++;
        k++;
    }

    while (j <= t) {
        ret[k] = v[j];
        j++;
        k++;
    }

    // 把 ret 里已排好序的元素放回 v 里
    for (int x = s; x <= t; x++) {
        v[x] = ret[x - s];
    }

    cout << "s=" << s << ", t=" << t << endl;
    PrintVector(v);

}

int main() {

//    vector<int> v = {3, 2, 1, 5, 8, 0, 7};
    vector<int> v = RandomVector(0, 20, 10);
    PrintVector(v);
    cout << "*****************" << endl;
    msort(v, 0, v.size() - 1);
    cout << "*****************" << endl;
    PrintVector(v);

    return 0;
}

